#include "stdafx.h"
#include<iostream>
#include<cstring>
#include<vector>
#include<fstream>
using namespace std;

int mod=99991;
int base=5;
unsigned long long powers[20]={1, 5, 25, 125, 625, 3125, 15625, 78125L, 390625L, 1953125L, 9765625L, 48828125L, 244140625L, 1220703125L, 6103515625L, 30517578125L, 152587890625L, 762939453125L, 3814697265625L, 19073486328125L};
int toNum(char c)
{
	if(c=='A')return 1;
	else if(c=='C')return 2;
	else if(c=='G')return 3;
	else if (c=='T')return 4;
	else return 0;
}

int Hash(char *word,int index,int m,long long code,int power)
{
	long long newCode=code%power;
	newCode *= base;
	newCode += toNum(word[index]);
	return newCode;
}

int CountMatches(char *dna,char *word)
{
	int m=strlen(word);
	int n=strlen(dna);
	long long wordCode=0;
	long long code=0;
	for(int i=0;i<m;i++)
	{
		code*=base;
		code+=toNum(dna[i]);

		wordCode*=base;
		wordCode+=toNum(word[i]);
	}
	long long power=powers[m-1];
	/*for(int i=0;i<m-1;i++)
	{
		power *= base;
	}*/
	int cnt=0;
	if(code==wordCode)
	{
		/*bool same=1;
		for(int i=0;i<m;i++)
		{
			if(dna[i]!=word[i])
			{
				same=0;
				break;
			}
		}
		if(same)
		{*/
			cnt++;
		//}
	}

	for(int i=m;i<n;i++)
	{
		code=Hash(dna,i,m,code,power);
		if(code==wordCode)
		{
			/*bool same=1;
			for(int j=i-m+1,k=0;k<m;k++,j++)
			{
				if(dna[j]!=word[k])
				{
					same=0;
					break;
				}
			}
			if(same)
			{*/
				cnt++;
		//	}
		}
	}
	return cnt;
}

void Run()
{
	int numberOfWords;
	cin>>numberOfWords;
	char *dna=new char[100000];
	cin>>dna;
	char *word;
	vector<char*>words;
	for(int i=0;i<numberOfWords;i++)
	{
		word=new char[20];
		cin>>word;
		words.push_back(word);
	}
	for(int i=0;i<words.size();i++)
	{
		cout<<CountMatches(dna,words[i])<<" ";
	}
	cout<<endl;
}

int main()
{
	int t;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		Run();
	}

	return 0;
}

